1767E - Algebra Flash - CodeForces Solution

#include <bits/stdc++.h>

#define pb push_back
#define fi first
#define se second

typedef long long ll;

using namespace std;

const int N = 300005, M = 45, MOD = 998244353, MX = 1e5, OFFSET = 1000001;
const int F = 0, T = 1;

int a[N], cost[M];
bool impossible[M][M];
int n, m, sum;
bool used[M];
long long deactivatableColors;

bool in(long long mask, int color) {
    return (1ll << color) & mask;
}

inline void include(long long& mask, int color) {
    mask |= (1ll << color);
}

inline void exclude(long long& mask, int color) {
    if (in(mask, color))
        mask ^= (1ll << color);
}

void combine_N_layer(long long &N_layer, long long discovered, int color) {
    for (int i = 1; i <= m; i++)
        if (impossible[color][i] && !in(discovered, i))
            include(N_layer, i);
}

void make_true(const long long &immediate_N_layer, long long &N_layer, long long &discovered) {
    for (int j = 1; j <= m; j++) {
        if (in(immediate_N_layer, j)) {
            exclude(N_layer, j);
            include(discovered, j);
        }
    }

    for (int j = 1; j <= m; j++) {
        if (in(immediate_N_layer, j))
            combine_N_layer(N_layer, discovered, j);
    }
}

int go_N_layer(long long N_layer, long long discovered = 0, int last = 1) {

    if (!N_layer) {
        return sum;
    }
    int mx = sum;
    for (int i = last; i <= m; i++) {
        if (in(N_layer, i)) {

            include(discovered, i);
            exclude(N_layer, i);

            long long immediate_N_layer = 0;
            combine_N_layer(immediate_N_layer, discovered, i);

            if (in(deactivatableColors, i)) {
                sum += cost[i];

                long long new_N_layer = N_layer, new_Discovered = discovered;

                make_true(immediate_N_layer, new_N_layer, new_Discovered);

                mx = max(mx, go_N_layer(new_N_layer, new_Discovered, i + 1));

                sum -= cost[i];
            }

            combine_N_layer(N_layer, discovered, i);

            if (in(deactivatableColors, i)) {

                for (int j = 1; j <= m; j++) {
                    if (in(immediate_N_layer, j) && in(deactivatableColors, j)) {

                        sum += cost[j];

                        long long new_N_layer = N_layer, new_Discovered = discovered;

                        exclude(new_N_layer, j);
                        include(new_Discovered, j);

                        long long subimmediate_N_layer = 0;

                        combine_N_layer(subimmediate_N_layer, new_Discovered, j);

                        make_true(subimmediate_N_layer, new_N_layer, new_Discovered);

                        mx = max(mx, go_N_layer(new_N_layer, new_Discovered, i + 1));

                        sum -= cost[j];
                    }
                }
            } else
                mx = max(mx, go_N_layer(N_layer, discovered));

            return mx;
        }
    }

    return mx;
}

void solve() {

    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), used[a[i]] = true;

    int gSum = 0;
    long long N_layer = 0;
    for (int i = 1; i <= m; i++) {
        scanf("%d", &cost[i]);
        if (used[i]) {
            gSum += cost[i];
            include(deactivatableColors, i);
            include(N_layer, i);
        }
    }

    exclude(deactivatableColors, a[n]);
    exclude(deactivatableColors, a[1]);

    for (int i = 1; i < n; i++) {
        impossible[a[i]][a[i + 1]] = impossible[a[i + 1]][a[i]] = true;

        if (a[i] == a[i + 1])
            exclude(deactivatableColors, a[i]);
    }

    cout << gSum - go_N_layer(N_layer);


}

int main() {

//    freopen("input.txt", "r", stdin);
//    freopen(".out", "w", stdout);

    solve();


    return 0;
}